package com.c2b.algorithm.newcoder.tree;

/**
 * <a href="https://www.nowcoder.com/practice/7298353c24cc42e3bd5f0e0bd3d1d759?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj">合并二叉树</a>
 * <p>已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。</p>
 * 例如：两颗二叉树是:
 * <pre>
 *      Tree1:          Tree2:          merge:
 *          1               2                    3
 *         / \             / \                 /  \
 *        3   2           1   3     ==>       4    5
 *       /                 \   \             / \    \
 *      5                   4   7           5   4    7
 * </pre>
 * <p>数据范围：树上节点数量满足0≤n≤500，树上节点的值一定在32位整型范围内。
 * 进阶：空间复杂度O(1) ，时间复杂度O(n)</p>
 *
 * @author c2b
 * @since 2023/3/14 14:23
 */
public class BM0032MergeTrees_S {

    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null) {
            return t2;
        }
        if (t2 == null) {
            return t1;
        }
        final TreeNode head = new TreeNode(t1.val + t2.val);
        head.left = mergeTrees(t1.left, t2.left);
        head.right = mergeTrees(t1.right, t2.right);
        return head;
    }
}
